package shu;

import utils.Utils;

import java.util.Scanner;

public class _06TopK {

    /**
     * 求海量数据（正整数）按逆序排列的前k个数（topK），因为数据量太大，不能全部存储在内存中，只能一个一个地从磁盘或者网络上读取数据，
     * 请设计一个高效的算法来解决这个问题
     第一行：用户输入K，代表要求得topK
     随后的N（不限制）行，每一行是一个整数代表用户输入的数据
     用户输入-1代表输入终止
     请输出topK，从小到大，空格分割
     */

    static int[] heap;
    static int index = 0;
    static int k;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        heap = new int[k];
        int x = sc.nextInt();
        while (x != -1){
            deal(x);
            x = sc.nextInt();
        }
        printRs();
    }

    private static void printRs() {
        Utils.print(heap);
    }

    /**
     * 如果数据的数量小于k直接加入堆中
     * 如果等于k，直接堆化
     * @param x
     */
    public static void deal(int x){
        if (index < k){
            heap[index++] = x;
            if (index == k){
                //堆化
                makeMinHeap(heap);
            }
        }else {
            //x和堆顶进行比较,如果x大于堆顶，x将堆顶挤掉并向下调整
            if (heap[0] < x){
                heap[0] = x;
                MinHeapFixDown(heap,0,k);
                printRs();
            }
        }
    }

    public static void makeMinHeap(int[] a){
        int n = a.length;
        for (int i = n/2-1; i>=0 ;i--){
            MinHeapFixDown(a, i, n);
        }
    }

    public static void MinHeapFixDown(int[] a,int i,int n ){
        int left = 2*i+1;
        int right = 2*i+2;
        if (left>=n){
            return;
        }
        int min = left;
        if (right>=n){
            min = left;
        }else {
            if (a[right] < a[left]){
                min = right;
            }
        }
        if (a[i] <= a[min]){
            return;
        }
        swap(a,i,min);
        MinHeapFixDown(a,min,n);
    }

    public static void swap(int[] a,int i ,int j ){
        int temp = a[i];
        a[i] = a[j];
        a[j] =temp;
    }
}
